1. Field of the Invention
The present invention relates to a motion compensation method, and more particularly, to an object-based quad-tree mesh motion compensation method using a Greedy algorithm.
2. Description of the Related Art
A motion compensation technique, by which the amount of data is reduced by taking advantage of the redundancy of a moving picture on the time axis, is essential for moving picture encoding. In order to achieve motion compensation by which complicated or partial motion can be accurately represented, a conventional hierarchical grid interpolation (HGI) technique defines a quad-tree mesh structure for frame-unit moving picture encoding.
FIG. 1 is a block diagram schematically illustrating an HGI technique. First, quad-tree block segmentation is performed on a current image frame (It) on the basis of the variance of frame difference (VFD) of each block in the frame, in a block 100. To be more specific, first, a current image frame is segmented into square blocks having predetermined sizes. If the VFD of each block is greater than the reference value, the block is again divided into four square blocks having the same size. This process is repeated until the VFDs of all of the divided blocks are smaller than the reference value. Here, VFD denotes the variance of the frame difference between the current image frame (It) and the previous image frame (Itxe2x88x921).
Next, the motions of vertices are estimated from a quad-tree block segmentation result St to minimize motion compensation errors within blocks, and quad-tree mesh motion compensation is performed on the image signals within the block by interpolation using the estimation, as in element 102. As a consequence, a motion-compensated image (It) and a motion vector Mt corresponding to the current image frame (It) are obtained.
FIGS. 2(a) and 2(b) show the quad-tree blocks of a previous frame matched with the current frame by a quad-tree mesh structure. Each block can be transformed, so that complicated motions can be accurately compensated. Here, bound vertices (for example, 1, 2, . . . , 10 in FIG. 2(a)) are defined to maintain the shape of each block to be rectangular, and motion vectors (for example, MV1 through MV3 in FIG. 2(b)) are obtained by linear interpolation using the motion vector of two adjacent vertices. On the other hand, motion estimation is performed on control points (for example, o, p, . . . , y in FIG. 2(a)), the motion vectors of which must be estimated, to minimize an image frame motion compensation error. The motion vector of each pixel within a block is obtained by linear interpolation, using the motion vector of each estimated vertex, thereby compensating for the motion within a block.
Segmented quad-tree information is encoded and transmitted as described below. While each node in a quad-tree starting from root nodes is visited in a breadth-first system, the nodes are encoded xe2x80x980xe2x80x99 or xe2x80x981xe2x80x99 depending on whether they are terminal nodes. However, a minimum-sized block does not need to be encoded with xe2x80x980xe2x80x99. The motion vector of each of the control points is fixed length encoded.
A conventional motion compensation technique is for frame-based moving picture encoding, so that it is not suitable for object-based moving picture encoding. Block segmentation in a quad-tree structure reduces motion compensation error, but the transmission rate increases due to increments in quad-tree information and motion vector information caused by segmentation. Hence, the decision of the part of an image to be further segmented is related directly to the transmission rate-distortion performance, which is a scale indicating the effective utilization of a given transmission rate. However, in the prior art, quad-tree block segmentation and motion estimation are separately performed, so that the transmission rate-distortion performance is not directly considered.
An objective of the present invention is to provide a motion compensation method which defines an object-based quad-tree mesh structure capable of accurately compensating for complicated and partial motion.
Another objective of the present invention is to provide a block segmentation method in an object-based quad-tree mesh motion compensation method using the Greedy algorithm, by which the transmission rate-distortion performance of an object-based quad-tree mesh structure is improved.
To achieve the first objective, the present invention provides an object-based quad-tree mesh motion compensation method using the Greedy algorithm, the method including: (a) defining an object-based quad-tree mesh; (b) segmenting each block in an image frame, which is segmented into blocks of predetermined sizes, in order to form the object-based quad-tree mesh of the step (a); and (c) estimating the motions of vertices to minimize distortion during compensation of motions within the segmented block, and compensating for the motion of an image within the block. Here, the object-based quad-tree mesh is extensively defined so that it is suitable for an object-based technique, and quad-tree blocks are classified into virtual quadrature blocks not including any part of an object, and real quadrature blocks including part of an object, according to the type of object.
To achieve the second objective, the present invention provides a block segmentation method in an object-based quad-tree mesh motion compensation method using the Greedy algorithm, the method including: (a) forming blocks of predetermined sizes which surround an object within an image; (b) segmenting each block to form an object-based quad-tree mesh; (c) calculating the segmentation gains of the segmented blocks; (d) again segmenting the block having a maximum segmentation gain to form an object-based quad-tree mesh; (e) again calculating the segmentation gains of blocks which are affected by the segmentation of the step (d); and (f) returning to the step (d) if a current transmission rate is smaller than a given transmission rate.